#include<vector>
#include<unordered_map>
#include<string>
using namespace std;

class Solution {
    int findParent(vector<int>& parents, int x) {
        return x == parents[x] ? x : parents[x] = findParent(parents, parents[x]);
    }
    void merge(vector<int>& parent, int x, int y) {
        int px = findParent(parent, x);
        int py = findParent(parent, y);
        if (px != py) parent[py] = px;
    }
public:
    vector<string> trulyMostPopular(vector<string>& names, vector<string>& synonyms) {
        unordered_map<int, vector<int>>graph;
        unordered_map<string, int>nameToid;
        unordered_map<int, string>idToname;
        int id = 0;
        for (auto& synonym : synonyms) {
            int split = synonym.find(',');
            string left = synonym.substr(1, split - 1);
            string right = synonym.substr(split + 1, synonym.size() - split - 2);
            if (nameToid.find(left) == nameToid.end()) {
                nameToid[left] = id;
                idToname[id] = left;
                ++id;
            }
            if (nameToid.find(right) == nameToid.end()) {
                nameToid[right] = id;
                idToname[id] = right;
                ++id;
            }
            graph[nameToid[left]].push_back(nameToid[right]);
        }
        vector<int>parents(id);
        for (int i = 0; i < parents.size(); ++i) parents[i] = i;
        for (auto& kv : graph) {
            for (auto& to : kv.second) {
                merge(parents, kv.first, to);
            }
        }
        unordered_map<int, string>pMap;
        for (int i = 0; i < id; ++i) {
            int pi = findParent(parents, i);
            if (pMap.find(pi) == pMap.end() || pMap[pi] > idToname[i]) {
                pMap[pi] = idToname[i];
            }
        }
        unordered_map<int, int>count;
        for (auto& name_ : names) {
            int split = name_.find('(');
            string name = name_.substr(0, split);
            int cnt = atoi(name_.substr(split + 1, name_.size() - split - 2).c_str());
            if (nameToid.find(name) != nameToid.end()) {
                int id = nameToid[name];
                count[findParent(parents, id)] += cnt;
            }
            else {
                pMap[id] = name;
                count[id] = cnt;
                ++id;
            }
        }
        vector<string>res;
        for (auto& kv : count) {
            int id = kv.first;
            string name = pMap[id];
            int cnt = kv.second;
            res.push_back(name + "(" + to_string(cnt) + ")");
        }
        return res;
    }
};

int main() {
    vector<string> names = { "Fcclu(70)","Ommjh(63)","Dnsay(60)","Qbmk(45)","Unsb(26)","Gauuk(75)","Wzyyim(34)","Bnea(55)","Kri(71)","Qnaakk(76)","Gnplfi(68)","Hfp(97)","Qoi(70)","Ijveol(46)","Iidh(64)","Qiy(26)","Mcnef(59)","Hvueqc(91)","Obcbxb(54)","Dhe(79)","Jfq(26)","Uwjsu(41)","Wfmspz(39)","Ebov(96)","Ofl(72)","Uvkdpn(71)","Avcp(41)","Msyr(9)","Pgfpma(95)","Vbp(89)","Koaak(53)","Qyqifg(85)","Dwayf(97)","Oltadg(95)","Mwwvj(70)","Uxf(74)","Qvjp(6)","Grqrg(81)","Naf(3)","Xjjol(62)","Ibink(32)","Qxabri(41)","Ucqh(51)","Mtz(72)","Aeax(82)","Kxutz(5)","Qweye(15)","Ard(82)","Chycnm(4)","Hcvcgc(97)","Knpuq(61)","Yeekgc(11)","Ntfr(70)","Lucf(62)","Uhsg(23)","Csh(39)","Txixz(87)","Kgabb(80)","Weusps(79)","Nuq(61)","Drzsnw(87)","Xxmsn(98)","Onnev(77)","Owh(64)","Fpaf(46)","Hvia(6)","Kufa(95)","Chhmx(66)","Avmzs(39)","Okwuq(96)","Hrschk(30)","Ffwni(67)","Wpagta(25)","Npilye(14)","Axwtno(57)","Qxkjt(31)","Dwifi(51)","Kasgmw(95)","Vgxj(11)","Nsgbth(26)","Nzaz(51)","Owk(87)","Yjc(94)","Hljt(21)","Jvqg(47)","Alrksy(69)","Tlv(95)","Acohsf(86)","Qejo(60)","Gbclj(20)","Nekuam(17)","Meutux(64)","Tuvzkd(85)","Fvkhz(98)","Rngl(12)","Gbkq(77)","Uzgx(65)","Ghc(15)","Qsc(48)","Siv(47)" };
    vector<string> synonyms = { "(Gnplfi,Qxabri)","(Uzgx,Siv)","(Bnea,Lucf)","(Qnaakk,Msyr)","(Grqrg,Gbclj)","(Uhsg,Qejo)","(Csh,Wpagta)","(Xjjol,Lucf)","(Qoi,Obcbxb)","(Npilye,Vgxj)","(Aeax,Ghc)","(Txixz,Ffwni)","(Qweye,Qsc)","(Kri,Tuvzkd)","(Ommjh,Vbp)","(Pgfpma,Xxmsn)","(Uhsg,Csh)","(Qvjp,Kxutz)","(Qxkjt,Tlv)","(Wfmspz,Owk)","(Dwayf,Chycnm)","(Iidh,Qvjp)","(Dnsay,Rngl)","(Qweye,Tlv)","(Wzyyim,Kxutz)","(Hvueqc,Qejo)","(Tlv,Ghc)","(Hvia,Fvkhz)","(Msyr,Owk)","(Hrschk,Hljt)","(Owh,Gbclj)","(Dwifi,Uzgx)","(Iidh,Fpaf)","(Iidh,Meutux)","(Txixz,Ghc)","(Gbclj,Qsc)","(Kgabb,Tuvzkd)","(Uwjsu,Grqrg)","(Vbp,Dwayf)","(Xxmsn,Chhmx)","(Uxf,Uzgx)" };
    Solution sol;
    sol.trulyMostPopular(names, synonyms);
}